% !TeX spellcheck = fr_FR
\documentclass{beamer}

\usepackage{pgf,pgfpages}
\usepackage{graphicx}
%\usepackage{units}
\usepackage[utf8]{inputenc}
\usepackage{listings}
\mode<presentation>
{
  \usetheme{ift}
  \setbeamercovered{transparent}
  \setbeamertemplate{items}[square]
}

\usefonttheme[onlymath]{serif}
\setbeamerfont{frametitle}{size=\LARGE,series=\bfseries}

\definecolor{uibred}{RGB}{170, 0, 0}
\definecolor{uibblue}{RGB}{0, 84, 115}
\definecolor{uibgreen}{RGB}{119, 175, 0}
%\definecolor{uibgreen}{RGB}{50, 105, 0}
\definecolor{uiborange}{RGB}{217, 89, 0}


\beamertemplatenavigationsymbolsempty


%\include{macros}

%\includeonlyframes{current}


\defbeamertemplate{enumerate item}{mycircle}
{
  %\usebeamerfont*{item projected}%
  %\usebeamercolor[bg]{item projected}%
  \begin{pgfpicture}{0ex}{0ex}{1.5ex}{0ex}
	%\pgfcircle[fill]{\pgfpoint{0pt}{.75ex}}{1.25ex}
    \pgfbox[center,base]{\color{uibblue}\insertenumlabel.}
  \end{pgfpicture}%
}
[action]
{\setbeamerfont{item projected}{size=\scriptsize}}
\setbeamertemplate{enumerate item}[mycircle]

\lstset{
 	language=C,
% 	captionpos=b,
 	tabsize=3,
 	frame=lines,
 	keywordstyle=\color{blue},
 	commentstyle=\color{gray},
 	stringstyle=\color{green},
	extendedchars=true,
% 	numbers=left,
 	numberstyle=\tiny,
 	numbersep=5pt,
 	breaklines=true,
 	showstringspaces=false,
 	basicstyle=\footnotesize\ttfamily,
 	emph={label},
 	inputencoding=utf8,
 	extendedchars=true,
  literate=%
  {é}{{\'{e}}}1
  {è}{{\`{e}}}1
  {ê}{{\^{e}}}1
  {ë}{{\¨{e}}}1
  {û}{{\^{u}}}1
  {ù}{{\`{u}}}1
  {â}{{\^{a}}}1
  {à}{{\`{a}}}1
  {î}{{\^{i}}}1
  {ç}{{\c{c}}}1
  {Ç}{{\c{C}}}1
  {É}{{\'{E}}}1
  {Ê}{{\^{E}}}1
  {À}{{\`{A}}}1
  {Â}{{\^{A}}}1
  {Î}{{\^{I}}}1
    }


\title{Certainty-factor-like structures in Bayesian belief networks}
\author{
Présentateurs: NGUYEN Van Tho, KHONG Minh Thanh\\
\vspace{0.2cm}
\vspace{0.2cm}
Professeur: Benoit Gaudou}

\institute{
Promotion 17\\
Institut de la Francophonie pour l'Informatique
}
\date{}

\AtBeginSection[]
{
\addtocounter{framenumber}{-1}
\begin{frame}<beamer>{Table of Contents}
\tableofcontents[currentsection,currentsubsection, 
    hideothersubsections, 
    sectionstyle=show/shaded,
]
\end{frame}
}

\begin{document}


%\setbeamertemplate{background}
% {\includegraphics[width=\paperwidth,height=\paperheight]{ifi}}
%\setbeamertemplate{footline}[default]

\begin{frame}
  \vspace{1cm}
  \titlepage
  \vspace{1cm}
\end{frame}

%
% Set the background for the rest of the slides.
% Insert infoline at the end
%
\setbeamertemplate{background}
 {\includegraphics[width=\paperwidth,height=\paperheight]{slide_bg}}
\setbeamertemplate{footline}[ifttheme]

\begin{frame}
  \frametitle{Plan}
  \addtocounter{framenumber}{-1}
  \tableofcontents
\end{frame}
%--------------------------------------------------------------------
%                          Introduction
%--------------------------------------------------------------------
\section{Introduction}
\begin{frame}
 \frametitle{Introduction}
 Certainty-factor model était populaire dans les années 80s. Mais après, il est souvent critiqué par les recherches comme: 
 \begin{itemize}
%  \item It is recommended that those who intend to build a system incorporating the certainty factor model consider these more general techniques ( Bayesian belief networks)
  \item  Le calcul pour combiner les facteurs de certitude 1/4 est surtout intéressante pour son importance historique
  \item il n'est pas possible de capturer un raisonnement à l'incertitude de règles d'inférence pour les règles de production
 \item \dots
 \end{itemize}
  
  Le but de cet article est de retrouver la relation entre la probabilité avec le modèle de facteur de certitude, mais à partir du point de vue des Réseaux Bayésiens.
\end{frame}
%--------------------------------------------------------------------
%                          Certainly-factor model
%--------------------------------------------------------------------
\section{Facteur de certitude (CF)}
\begin{frame}
 \frametitle{Facteur de certitude (CF)}
 La mesure que $e$ implique $h$:
 
\textbf{si $e$, alors $h_{CF(h,e)}$}
 
 CF($e\rightarrow h$)  est une valeur numérique comprise entre -1 et +1 dont
 l'interprétation est la suivante :
 \begin{itemize}
 \item si CF($e\rightarrow h$) $\ge$ 0, alors CF($e\rightarrow h$) mesure la certitude que $e$
  confirme $h$, i.e. que $e$ permet de dériver $h$
 \item si CF($e\rightarrow h$) $\le$ 0, alors -CF($e\rightarrow h$) mesure la certitude que $e$ infirme $h$, i.e. que $e$ permet de dériver non($h$)
 \end{itemize}
 
 \begin{center}
 $e \stackrel{CF(h,e)}{\longrightarrow} h$
 \end{center}
\end{frame}
%--------------------------------------------------------------------
\begin{frame}
\frametitle{Fonction de combinaison}
Si on a:
\begin{center}
 $e' \stackrel{CF(e,e')}{\longrightarrow} e \stackrel{CF(h,e)}{\longrightarrow} h$
\end{center}
Alors:
\begin{center}
 $CF(h,e')= CF(h,e) * max{0, CF(e,e')}$
\end{center}
%$CF(e, e')$ indique 
\end{frame}
%--------------------------------------------------------------------
\begin{frame}
\frametitle{Fonction de combinaison(suit)}
Si on a:
\begin{figure}[ht]
	\begin{center}
	  \includegraphics[width=4cm]{images/Selection_020.png}
	\end{center}
\end{figure}

Alors:
\begin{center}
 $CF(e_{1}$ et $e_{2},e')= min\{CF(e_{1},e'), CF(e_{2},e')\}$
\end{center}

\begin{center}
 $CF(e_{1}$ ou $e_{2},e')= max\{CF(e_{1},e'), CF(e_{2},e')\}$
\end{center}
%$CF(e, e')$ indique 
\end{frame}
%--------------------------------------------------------------------
\begin{frame}
\frametitle{Fonction de combinaison(suit)}
\begin{figure}[ht]
	\begin{center}
	  \includegraphics[width=3cm]{images/Selection_021.png}
	\end{center}
\end{figure}
Alors:
 \[CF(h,e'_{1}\ \textbf{co}\ e'_{2}) =
   \begin{cases}
    x + y - x*y & \text{if } x > 0, y > 0 \\
    x + y + x*y & \text{if } x < 0, y < 0 \\
  \dfrac{(x + y)}{1 - min\{|x|, |y|\}}         & \text{if otherwise.}  
   \end{cases}\]
Où: \ \ \ \ \ \ $CF(h, e'_{1}) = x$ and $CF(h, e'_2) = y$
\end{frame}
%--------------------------------------------------------------------
\begin{frame}
\frametitle{Fonction de combinaison(suit)}
On considère un exemple: 
\begin{itemize}
\item R1: if $flu$  then $fever_{CF(fever, flu) = 0.8}$
\item R2: if $common-cold$  then $fever_{CF(fever, common-cold) = 0.3}$
\end{itemize}
On suppose que:\\
\begin{center}
$CF(flu, e') = 0.6$,\\
$CF(common-cold, e') = 1$
\end{center}

Alors\\
\begin{center}
$CF(h,flu\ \textbf{co}\ common-cold)$ = ?
\pause
$= 0.636$
\end{center}

\end{frame}

%--------------------------------------------------------------------
%                          Bayesian belief networks
%--------------------------------------------------------------------
\section{Réseaux Bayésiens}
\begin{frame}
 \frametitle{Réseaux Bayésiens}
\begin{itemize}
 \item Un graphe orienté acyclique
 \item Chaque nœud est annoté d’une table de probabilités
conditionnelle
\end{itemize}
 
 \begin{center}
  \includegraphics[width=6cm]{images/wp.png}
 \end{center}

\end{frame}
%--------------------------------------------------------------------
%		Certainty-factor interpretation of Bayesian belief networks
%--------------------------------------------------------------------
\section{CF et Réseaux Bayésiens}
\begin{frame}
 \frametitle{CF et Réseaux Bayésiens}
 \begin{itemize}
\item Notation utilisée
\item Causale indépendante
\item Noisy-OR model
\item Noisy-MAX model
\item Noisy-AND model
\item Noisy-MIN model
\item Propagation of evidence
 \end{itemize}

\end{frame}
%--------------------------------------------------------------------
%\subsection{Employed notation}
\begin{frame}
 \frametitle{Notation utilisée}
 Nous utilisons les notions: 
 \begin{itemize}
 \item Les variables en majuscule: X, Y,\dots
 \item Les valeurs en minuscule: $X = x$ veut dire que $X=true$, $X= \neg x$ dire que $X=false$ \dots
 \item Tous les variables sont discrètes
 \item $\sum_{f(X_1,...,X_n) = c}^{}\psi(X_1,...,X_n)$: la somme des valeurs de la fonction $\psi$ avec la contrainte: $f(X_1,...,X_n) = c$
 \end{itemize}

 
 
\end{frame}
%--------------------------------------------------------------------
%\subsection{Causal independence}
\begin{frame}
 \frametitle{Causale indépendante}
 Pour construire le réseaux Bayésien, utiliser la causale indépendante est prometteuse.
 \begin{figure}[ht]
 	\begin{center}
 	  \includegraphics[width=3cm]{images/Selection_022.png}
 	\end{center}
 \end{figure}
L'idée c'est que $C_1,...,C_n$ influencent $E$ par les variables intermédiaires: $I_1,..,I_n$ et une déterministe fonction $f$. L'effet de $C_k$ sur $E$ est indépendante avec $C_j, j\ne k$ 

Quand $I_k = i_k, k= 1,..,n$ et $E = e$, on a: $e = f(i_1,..,i_n)$
\end{frame}
%--------------------------------------------------------------------
%\subsection{Causal independence}
\begin{frame}
 \frametitle{Causale indépendante}
 Pour calculer la probabilité de $P(e|C_1,..,C_n)$:
\begin{itemize}
\item  $P(e|C_1,..,C_n) = \sum_{f(I_1,..,I_n)=e} P(e|I_1,..,I_n, C_1,..,C_n) P(I_1,..,I_n|C_1,..,C_n)$
 
\end{itemize}

 
 Comme les causales sont indépendantes: 
 \begin{itemize}
 \item $P(e|I_1,..,I_n, C_1,..,C_n) = P(e|I_1,..,I_n)$
 \item $P(I_1,..,I_n|C_1,..,C_n) = \prod_{k=1}^{n} P(I_k|C_k)$
 \end{itemize}
 
 
 On obtient:
 \begin{itemize}
	\item  $P(e|C_1,..,C_n) = \sum_{f(I_1,..,I_n)=e} P(e|I_1,..,I_n) * \prod_{k=1}^{n} P(I_k|C_k)$
 \end{itemize}

 Les exemples du modèle de causale indépendante sont \textbf{Noisy-OR}, \textbf{Noisy-MAX, Noisy-AND, Noisy-MIN}.
 
\end{frame}
%--------------------------------------------------------------------
%\subsection{Noisy-OR model}
\begin{frame}
 \frametitle{Modèle Noisy-OR}
 Pour simplifier, nous utilisons le modèle ci-dessous:
  	\begin{center}
  	  \includegraphics[width=2.5cm]{images/Selection_023.png}
  	\end{center}
  Maintenant, supposant que trois variables A, B et C sont
  binaire, et que nœud C représente un logique OR:
 \[P(c|A,B) =
   \begin{cases}
    0 & \text{if } A = \neg a  \text{ and } B= \neg b\\
    1       & \text{otherwise }
   \end{cases} \]
Donc P(c) = 
\pause
 $= \sum_{A,B}^{} P(c|A,B) * P(A,B)$
 $= P(a)P(b) + P(\neg a)P(b) + P(a)P(\neg b)$
 $= P(a) + P(b) - P(a)P(b)$

$\implies$ C'est exactement comme la fonction de combinaison
\end{frame}
%--------------------------------------------------------------------
%\subsection{Noisy-MAX model}
\begin{frame}
 \frametitle{Modèle Noisy-MAX}

 Maintenant, dans le modèle \textbf{noisy-MAX}, les variables ne sont plus binaires. Sans perdre de la généralité, supposant que A, B, C peut recevoir les valeurs: $a_1, b_1, c_1,..., a_3, b_3, c_3$ et $a_1 > a_2 > a_3$, $a_1 = b_1 = c_1$ \dots
  \[
   g(A,B) =
    \begin{cases}
     c_1 & \text{if } A =  a_1  \text{ or } B=  b_1\\
     c_2 & \text{if } A =  a_2  \text{ or } B=  b_2\\
      & \text{and } A \ne a_1 \text{ and }  B \ne b_1\\
     c_3       & \text{otherwise }
    \end{cases}
  \]
 Où $g(A,B) = C$
 
 Question: $P(c_1)$ = ?\\
 \pause
 $=\sum_{g(A,B) = c_1}{}P(A)P(B)= P(a_1) + P(b_1) - P(a_1) * P(b_1)$\\
 
 C'est comme la fonction de combinaison.\\
 \textbf{Mais c'est vrai pour $P(c_2), P(c_3)$?}
\end{frame} 
%--------------------------------------------------------------------
\begin{frame}
 \frametitle{Modèle Noisy-MAX}
  \[
   g(A,B) =
    \begin{cases}
     c_1 & \text{if } A =  a_1  \text{ or } B=  b_1\\
     c_2 & \text{if } A =  a_2  \text{ or } B=  b_2\\
      & \text{and } A \ne a_1 \text{ and }  B \ne b_1\\
     c_3       & \text{otherwise }
    \end{cases}
  \]
  Appliquer la définition on obtient:
  
 $P(c_2) = P(a_2)(P(b_2) + P(b_3)) + P(b_2)P(a_3)$
 $\ne P(a_2) + P(b_2) - P(a_2) P(b_2)$\\
 
 
 $\implies$ Le CF ne peut pas présenter \textbf{Noisy-MAX} dans ce cas
\end{frame} 
%--------------------------------------------------------------------
%\subsection{Noisy-AND model}
\begin{frame}
 \frametitle{Modèle Noisy-AND}
 \begin{center}
  \includegraphics[width=2cm]{images/and.png}
 \end{center}
 Utilisé quand on veut modéliser l'effet conjonctif des causes, 
 
 Trois variables A, B et C sont
 binaire, et que nœud C représente une logique AND:
 \[
  P(c|A,B) =
   \begin{cases}
    1 & \text{if } A =  a \text{ and } B=b\\
    0       & \text{otherwise }
   \end{cases}
 \]
Donc P(c) = 
\pause
 $\sum_{A,B}^{} P(c|A,B) * P(A,B)$
\pause
 $= P(a)P(b)$

$\implies$ C'est différent de la fonction de combinaison
\end{frame}
\begin{frame}
 \frametitle{Modèle Noisy-AND(suit)}
 %modify
 En utilisant:
 \begin{itemize}
 \item  si a alors $b_{P(b)}$
 \item  si b alors $c_{1.0}$
 \end{itemize}

 Le modèle Noisy-AND peut être mis en correspondance avec le modèle CF.
\end{frame}
%--------------------------------------------------------------------
%\subsection{Noisy-MIN model}
\begin{frame}
 \frametitle{Modèle Noisy-MIN}
 Une généralité du modèle Noisy-AND pour les variables -binaires
  \[
   g(A,B) =
    \begin{cases}
     c_3 & \text{if } A =  a_3  \text{ or } B=  b_3\\
     c_2 & \text{if } A =  a_2  \text{ or } B=  b_2\\
      & \text{and } A \ne a_3 \text{ and }  B \ne b_3\\
     c_1       & \text{otherwise }
    \end{cases}
  \]
  Appliquer la définition on obtient:
 \begin{itemize}
  \item $P(c_1) =  \sum_{g(A,B)=c1}^{} P(A) * P(B)$\\
 $=\sum_{A=a_1 \wedge B=b_1}^{} P(A)*P(B)=P(a_1)*P(b_1)$
\item 
 $P(c_i) = P(a_i, b_i) + \sum_{j=1}^{i-1} (P(a_i, b_j) + P(a_j, b_i))$\\
 \item $P(c_2) = P(a_2, b_2) + P(a_2, b_1) + P(a_1, b_2)$\\
\end{itemize}
 
 $\implies$ 
 \begin{itemize}
  \item $P(c_1)$ est comme le modèle noisy-AND
  \item $P(c_2)$ et $P(c_3)$: Il n'y a pas de correspondance.
  \item Le CF ne peut pas complètement présenter \textbf{Noisy-MIN}
 \end{itemize}
 
\end{frame}
%--------------------------------------------------------------------
%\subsection{Propagation of evidence}
\begin{frame}
 \frametitle{Propagation}
 
 \begin{center}
  \includegraphics[width=2cm]{images/pro.png}
 \end{center}
 $P(C|D) =  \sum_{A,B}^{} P(C,A,B|D)$\\
 $P(C|D) =  \sum_{A,B}^{} P(C|A,B)*P(A|B,D) * P(B|D)$\\
 $P(C|D) =  \sum_{A,B}^{} P(C|A,B)*P(A|D) * P(B)$\\
 
 Quand D=d:
 
 $P(c|d) = P(a|d)*P(b) + P(a|d)*P(\neg b) + P(\neg a|d)*P(b)$ \\
\hspace*{1cm}$=P(a|d) + P(b) - P(a|d)*P(b) $\\
$\implies$ La propagation est dans ce cas est d'accord avec le modèle CF
\end{frame}

\begin{frame}
 \frametitle{Propagation(suit)}
 Quand D est avec P(d):
 \vspace*{0.3cm}
 
 $P(C) =  \sum_{A,B,D}^{} P(C,A,B,D)$\\
\hspace*{1cm}$= \sum_{A,B,D}^{} P(C,A,B|D)P(D)$\\
\hspace*{1cm}$= \sum_{A,B,D}^{} P(C|A,B)P(A|D)P(B)P(D)$\\
 \vspace*{0.5cm}
 
 $P(c) = P(c|d)*P(d) + P(c|\neg d)*P(\neg d)$ \\
\hspace*{1cm}$=(P(a|d) + P(b) - P(a|d)*P(b))P(d) + P(b)P(\neg d) $\\
\hspace*{1cm}$=P(a|d)P(d) + P(b) - P(a|d)P(d)P(b)$\\
 \vspace*{0.3cm}
 
$\implies$ La propagation est dans ce cas est d'accord avec le modèle CF
\end{frame}

%--------------------------------------------------------------------
%\section{Practical significance}
%\begin{frame}
% \frametitle{Practical significance}
% \begin{itemize}
%  \item Quand 
% \end{itemize}

%\end{frame}
%--------------------------------------------------------------------
%                          Conclusion
%--------------------------------------------------------------------
\section{Conclusion}
\begin{frame}
\frametitle{Conclusion}
Nous avons étudié la relation entre les réseaux bayésiens avec le modèle de facteur de certitude
\begin{itemize}
 \item Que les modèles probabilistes très spécifiques peuvent être traités de cette manière (Noisy-OR, Noisy-AND)
% \item Le modèle de facteur de certitude est plus important que les recherches pensent
%% \begin{itemize}
%% \item fin
%% \end{itemize}
\item Le modèle CF est plus importance que la plupart des chercheurs pensent
\end{itemize}
\end{frame}
%--------------------------------------------------------------------
%--------------------------------------------------------------------
%--------------------------------------------------------------------
%--------------------------------------------------------------------
\section*{Références}
\begin{frame}
\frametitle{Références}
\begin{thebibliography}{9}
\item  Lucas, Peter JF. "Certainty-factor-like structures in Bayesian belief networks." Knowledge-based systems 14.7 (2001): 327-335.

\end{thebibliography}
\end{frame}
%--------------------------------------------------------------------
\section*{}
\begin{frame}
\begin{center}
\huge Merci pour votre attention!
\end{center}

\end{frame}
\end{document}
